package tree;

import java.util.ArrayList;

/**
 * 题目：求二叉树的下一个节点
 * 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回 。
 * 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
 * <p>
 * 解题思路：
 * 先根据给的节点找到这个二叉树的根节点，然后求出中序序列放到一个list里面，然后再根据给定的值求下一个节点。
 *
 * @Author Gavin
 * @date 2022.08.06 21:23
 */
public class tree_20 {
    public static ArrayList<TreeNode> list = new ArrayList<>();

    public TreeNode solution(TreeNode node) {
        if(node==null)return null;
        TreeNode root = node;
        while (root.next != null) {
            root = root.next;//本题目中next指向父节点，所以先找到父节点
        }
        inOrder(root);//得到中序遍历的结果集

        for (int i = 0; i < list.size(); i++) {
            if (node == list.get(i)) {//遍历中序集合，找到node节点的下一个节点
                return i == list.size() - 1 ? null : list.get(i + 1);
            }
        }
        return null;
    }

    void inOrder(TreeNode pNode) {
        if (pNode != null) {
            inOrder(pNode.left);
            list.add(pNode);
            inOrder(pNode.right);
        }
    }
}
